package com.example.sorts12.sorts;

/**
 * 归并排序算法
 * @auther lijiewei
 * @date 2021/8/27 15:36
 */
public class MergeSort {

    /**
     * 归并排序算法
     * @param a 数组
     * @param n 数组大小
     * @return
     * @author lijiewei
     * @date   2021/8/27 15:48
     */
    public static void mergeSort(int[] a, int n) {
        mergeSortinternally(a, 0, n-1);
    }

    /**
     * 递归调用函数
     * @param a 数组
     * @param p 开始下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/27 15:53
     */
    private static void mergeSortinternally(int[] a, int p, int r) {
        //递归终止条件
        if (p >= r) {
            return;
        }

        //取 p 到 r 之间的中间位置，防止（p+r）的和超过int最大值
        int q = p + (r-p)/2;
        //分治递归
        mergeSortinternally(a, p, q);
        mergeSortinternally(a, q+1, r);

        //将A[p...q]和A[q+1...r]合并为A[p...r]
//        merge(a, p, q, r);
        mergeBySentry(a, p, q, r);
    }

    /**
     * 合并数组
     * @param a 数组
     * @param p 开始下标
     * @param q 中间下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/27 16:08
     */
    private static void merge(int[] a, int p, int q, int r) {
        //用于遍历的指针
        int i = p;
        int j = q+1;
        int k = 0;

        //申请一个大小和a[p...r]一样的临时数组
        int[] tmp = new int[r-p+1];
        while (i<=q && j<=r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }

        //判断哪个子数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r) {
            start = j;
            end = r;
        }

        //将剩余的数据拷贝到临时数组tmp
        while(start <= end) {
            tmp[k++] = a[start++];
        }

        //将tmp中的数组拷贝回a[p...r]
        for (i = 0; i <= r-p; i++) {
            a[p+i] = tmp[i];
        }
    }


    /**
     * 合并数组（哨兵模式）
     * @param arr 数组
     * @param p 开始下标
     * @param q 中间下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/27 16:41
     */
    private static void mergeBySentry(int[] arr, int p, int q, int r) {
        //从p开始
        int[] leftArr = new int[q-p+2];
        //从q+1开始
        int[] rightArr = new int[r-q+1];

        for (int i = 0; i <= q-p; i++) {
            leftArr[i] = arr[p+i];
        }
        //第一个数组添加哨兵(最大值)
        leftArr[q-p+1] = Integer.MAX_VALUE;

        for (int i = 0; i < r-q; i++) {
            rightArr[i] = arr[q+1+i];
        }
        //第二组数组添加哨兵(最大值)
        rightArr[r-q] = Integer.MAX_VALUE;

        //循环指针
        int i = 0;
        int j = 0;
        int k = p;
        while(k <= r) {
            // 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
    }
}
